The invention relates to a method, a system, and a computer program for automatically detecting traffic circles in digital maps. In particular, the invention relates to a non-semantic automatic detection of traffic circles in digital maps.
Various applications which are based on digital maps, e.g. digital navigation systems, require an automatic detection of structures in a digital map. By way of example, if the digital map is changed, the automatic detection of structures may yield the ability to automatically detect changes that emerge from different map versions by one producer and/or from maps from different producers. In particular, the automatic detection of traffic circles, also known as roundabouts, in a street network of a digital map may lead to changes from an intersection to a traffic circle and/or modeling differences of a traffic circle between two maps from different producers being captured. To this end, a semantic attribute from the metadata of a structure of the digital map is often used to, for example, automatically detect or identify a traffic circle. If the information about the traffic circles in the digital map is stored semantically therein, then a traffic circle can be detected by way of the semantic information. To this end, a corresponding attribute of the metadata may be read. In the simplest case, this may be a Boolean value which is assigned to an intersection point or a street segment and which specifies whether the relevant structure belongs to a traffic circle. However, the evaluation of a semantic attribute for identifying a traffic circle in a digital map is only successful if this information is provided and correctly stored in the data model of the map. This may prevent an identification of traffic circles in digital maps if either this semantic attribute is not present in the digital map or this attribute is present but not correctly captured for some or all traffic circles.
It is therefore an object of the invention to provide an improved detection of traffic circles in digital maps. In particular, it is an object of the invention to provide an improved non-semantic automatic detection of traffic circles in digital maps.
According to the invention, this object is achieved by a method, a system, and a computer program in accordance with embodiments of the invention.
A method according to the invention serves to detect a traffic circle in a digital map. The method comprises a topological detection or determination of a cycle within a street graph of the digital map. A “cycle” within the scope of the present document should be understood to mean a path in the street graph of a digital map, in which the start and end vertex are the same and all vertices, apart from the identity of start vertex and end vertex, occur at most once. Such a cycle may be considered to be a candidate for a traffic circle if it consists only of trivalent and bivalent vertices, i.e. vertices from which exactly three or exactly two edges emerge.
The method calculates a similarity of an internal angle of a corner of the polygon, which corresponds to the cycle, with respect to an internal angle of a corresponding corner of a reference polygon. By way of example, the reference polygon can be a polygon which approximates a circle. By way of another example, the reference polygon can be a polygon which has the same number of corners as the polygon of the detected cycle. In general, the reference polygon can be a polygon which has a similarity to a circle and/or which is suitable for determining the similarity to the geometric form of the detected cycle. A similarity indicator is calculated on the basis of the calculated similarity of the internal angles of all corners of the polygon of the detected cycle in comparison with the internal angles of the corners of the reference polygon. If the similarity indicator exceeds a predefined threshold, the detected cycle is set as a traffic circle in the digital map.
By calculating a similarity indicator on the basis of the similarity of the interior angles of all corners of the polygon of a cycle to the interior angles of a reference polygon, it is possible to detect a traffic circle without semantic information. The method is able to automatically detect the traffic circle on the basis of a street graph in the digital map and set the detected cycle as a traffic circle. As a result of using a threshold, it is possible to efficiently exclude possible cycles which have a geometric similarity to a traffic circle that is too low. As a result, it is possible to ensure that possible errors in the topological detection of the traffic circles are reduced or even excluded.
In accordance with an advantageous configuration, the method may comprise determining a seed point in the street graph, wherein the seed point is a trivalent vertex of a street graph of the digital map. Proceeding from the determined seed point, a cycle can be determined within the street graph of the digital map by a breadth-first search or a depth-first search. Each possible path through the graph proceeding from the seed point is tracked at the latest until the detection of a cycle, i.e. in the case of an identity of start vertex and end vertex, for as long as the condition is satisfied that it only leads over trivalent or bivalent vertices and does not include any vertex which has already been visited. By way of example, an edge of a trivalent vertex may represent an entrance or exit path of the traffic circle. The two further edges of the trivalent vertex may, for example, represent a portion of the path along which it is possible to traverse the traffic circle. By using a trivalent vertex as a seed point, it is possible to efficiently determine an entrance path or exit path of a traffic circle. Hence, the search for cycles in the digital map can be calculated more efficiently.
In accordance with a further advantageous configuration, the reference polygon may be a polygon which has the same number of edges as the polygon of the detected cycle, and approximates a circle. Instead of comparing the similarity of a polygon of a cycle to a circle, a polygon which approximates the circular form of a traffic circle may be used as a reference. By using a reference polygon, it is possible to efficiently determine the similarity between the polygon of a cycle and the reference polygon. Hence, it is possible to increase the efficiency when calculating the similarity.
In accordance with a further advantageous configuration, the calculated similarity of the interior angle of each corner can be weighted by the geometric length of the edges of the polygon that belongs to the interior angle. Using this, the accuracy of the similarity determination can be efficiently improved. Further, the comparability of the similarity indicator can be increased.
In accordance with a further advantageous configuration, the detected cycle may consist only of vertices which are either trivalent or lead to a trivalent vertex again via one or more bivalent vertices. Using this, it is possible to efficiently restrict the detection of cycles to cycles which are possible candidates for traffic circles. As a result, the computational outlay for detecting cycles can be efficiently reduced.
In accordance with a further advantageous configuration, the similarity indicator CI can be calculated as follows:
  CI  =            ∑              i        =        1            n        ⁢                                        l                          i              -              1                                +                      l            i                                    2          ⁢          l                    ·              (                  1          -                                                                                    α                  i                                -                                  α                  c                                                                                                  360                ⁢                °                            -                              α                c                                                    )            where αc is the interior angle of the reference polygon,where αi is the interior angle of a corner i of the polygon of the cycle,where n is the number of corners of the polygon of the cycle,where li is the geometric length of the edge, proceeding from the corner i of the polygon of the cycle,where li−1 is the length of the edge, proceeding from the corner i−1 of the polygon of the cycle, andwhere l is the overall length of all edges of the polygon of the cycle.
Using this, it is possible to efficiently determine a weighted similarity of the interior angles of the polygon of a cycle. The calculation of the similarity indicator facilitates a uniform determination of the similarity of the geometric form of a cycle to the reference polygon, e.g. a polygon which ideally approximates a circle.
A system according to the invention serves to detect a traffic circle in a digital map, wherein the system is adapted to carry out the above-described method.
A computer program according to the invention comprises instructions which execute the above-described method when said instructions are executed on a computer.
Within the scope of the following document, a computer program or a computer program product should be understood to mean that this may also be a program element and/or a computer readable medium which comprises instructions for controlling a computer system to execute the above-described method.
The computer program may be embodied as computer-readable code in any suitable programming language, such as e.g. JAVA, C, and/or C++, and may be stored on a computer-readable medium (removable disk and/or volatile and/or non-volatile memory). The code may be adapted to program a computer or any other programmable appliance in order to obtain the intended functions. The computer program may be downloaded and/or provided by way of a network such as, for example, the Internet.
The invention can be realized by means of a computer program. However, the invention can also be realized by means of one or more electronic circuits or hardware modules, and/or by a combination of software modules and hardware modules.
The invention is based on the considerations presented below.
The method according to the invention is able to calculate a similarity of the geometry of a cycle within a road network that is described by a polygon, to a polygon having the same number of corners and coming closest to an ideal circle. It can be used within the scope of a two-stage method to identify traffic circles in a digital map. Here, in a first step, candidates for traffic circles are determined by virtue of searching for cycles in the digital map that correspond topologically to a traffic circle. In a second step, the geometric similarity to an ideal circular polygon with the same number of corners is determined for each candidate or cycle with the aid of a similarity metric or similarity indicator. If this similarity exceeds a specific, freely selectable threshold, for example 60%, the candidate is classified and/or set as a traffic circle.
In digital maps which only describe the topology and the geometry of the road network, it is nevertheless possible to identify traffic circles using the method according to the invention. The traffic circles detected thus can subsequently be mapped onto one another within the scope of a matching analysis, for example in order to reference the entrance and exit points over a plurality of maps. Such map-agnostic referencing facilitates, for example, the maintenance of learned location-related information when replacing and/or updating the digital map, and the comparison of maps for the purposes of quality assurance of automobile navigation systems.
Further features of the invention emerge from the claims, the figures, and/or the description of the figures. All the features and feature combinations mentioned above in the description and all features and feature combinations mentioned in the description of the figures and/or shown only in the figures are usable not only in the respectively specified combination, but also in other combinations or else on their own.
Other objects, advantages and novel features of the present invention will become apparent from the following detailed description of one or more preferred embodiments when considered in conjunction with the accompanying drawings.